""""1.老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。
用分治法解决该金块问题。用三分策略。"""
def find_max_min_ternary(arr, low, high):
    """
    使用三分策略同时找到数组中的最大值和最小值
    返回: (最大值, 最小值)
    """
    n = high - low + 1

    # 基本情况处理
    if n == 1:
        return arr[low], arr[low]
    elif n == 2:
        if arr[low] > arr[high]:
            return arr[low], arr[high]
        else:
            return arr[high], arr[low]

    # 将数组分成三部分
    third = n // 3
    mid1 = low + third
    mid2 = low + 2 * third

    # 递归处理三个子数组
    part1_max, part1_min = find_max_min_ternary(arr, low, mid1 - 1)
    part2_max, part2_min = find_max_min_ternary(arr, mid1, mid2 - 1)
    part3_max, part3_min = find_max_min_ternary(arr, mid2, high)

    # 合并结果
    overall_max = max(part1_max, part2_max, part3_max)
    overall_min = min(part1_min, part2_min, part3_min)

    return overall_max, overall_min


# 测试金块问题的三分策略
def test_gold_ternary():
    golds = [5, 2, 8, 1, 9, 3, 7, 4, 6]
    max_gold, min_gold = find_max_min_ternary(golds, 0, len(golds) - 1)
    print(f"金块重量: {golds}")
    print(f"最重金块(三分策略): {max_gold}")
    print(f"最轻金块(三分策略): {min_gold}")
    print()


test_gold_ternary()